# 给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
#  '?' 可以匹配任何单个字符。
# '*' 可以匹配任意字符串（包括空字符串）。
#  两个字符串完全匹配才算匹配成功。
#  说明:
#  s 可能为空，且只包含从 a-z 的小写字母。
#  p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
#
#  示例 1:
#  输入:s = "aa", p = "a"
# 输出: false
# 解释: "a" 无法匹配 "aa" 整个字符串。
#
#  示例 2:
#  输入:s = "aa", p = "*"
# 输出: true
# 解释:'*' 可以匹配任意字符串。
#
#  示例 3:
#  输入:s = "cb", p = "?a"
# 输出: false
# 解释:'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
#
#  示例 4:
#  输入:s = "adceb", p = "*a*b"
# 输出: true
# 解释:第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
#
#  示例 5:
#  输入:s = "acdcb", p = "a*c?b"
# 输出: false
class Solution:
    def isMatch2(self, s: str, p: str) -> bool:
        """
        贪心 + 回溯
        :param s:
        :param p:
        :return:
        """
        if not s or s == '':
            if p and p == '':
                return True
        elif not p or p == '':
            return False
        targetStrLen, patternLen = len(s), len(p)
        # s: abcdefgabcdefabc
        # p: abc?*e*f*abc
        sRight, pRight = targetStrLen - 1, patternLen - 1
        # 1.先从尾部开始匹配
        while pRight >= 0 and sRight >= 0 and p[pRight] != "*":  # 双指针逆序尾部比对（结束条件：字符不匹配、遇到*、超过起始）
            if s[sRight] == p[pRight] or p[pRight] == '?':
                sRight, pRight = sRight - 1, pRight - 1
            else:  # 有不匹配的字符说明不匹配，直接返回False
                return False
        if pRight == -1:  # 2.p 已经到达起始位置之前，只有s也到达起始位置之前才匹配，否则不匹配
            return sRight == -1
        # 3.双指针正序头部比对（结束条件：有一个到达右指针、匹配不成功）
        sLeft, pLeft = 0, 0
        pBackTrace, sBackTrace = -1, -1  # 用于记录p中出现*时，双指针s、p下标位置方便回溯
        while sLeft <= sRight and pLeft <= pRight:
            if (p[pLeft] == s[sLeft]) or (p[pLeft] == '?'):
                sLeft, pLeft = sLeft + 1, pLeft + 1
            elif p[pLeft] == '*':
                pLeft += 1  # 模式串指针右移（相当于 * 匹配''), 并记录p的回溯位置
                pBackTrace = pLeft
                sBackTrace = sLeft  # 记录s的回溯位置,方便后续贪心回溯
            elif sBackTrace != -1 and sBackTrace + 1 <= sRight:  # 若可回溯，则尝试将*多匹配一个字符
                sBackTrace += 1  # 贪心进行回溯
                sLeft = sBackTrace  # s在上次尝试的基础上，多走一个字符
                pLeft = pBackTrace  # p回溯到* 的下一个位置
            else:
                return False
        # 4.剩余检查：验证p剩余字符是否全为 *，否则匹配不成功
        for i in range(pLeft, pRight + 1):
            if p[i] != '*':
                return False
        return True

    def isMatch1(self, s: str, p: str) -> bool:
        """
        解法一：动态规划
        dp[i][j] 表示 s 的s[0:i + 1] 子串是否能匹配 p[0:j + 1] 的子串
        :param s:
        :param p:
        :return:
        """
        targetStrLen, patternLen = len(s), len(p)
        if patternLen == 1 and p[0] == "*":
            return True
        # dp[i][j] 表示 s 的s[0:i + 1] 子串是否能匹配 p[0:j + 1] 的子串
        dp = [[False] * (patternLen + 1) for _ in range(targetStrLen + 1)]
        # 初始化状态
        dp[0][0] = True  # 0列因为除了(0,0)都是false
        for j in range(1, patternLen + 1):
            if p[j - 1] == '*':  # '*'可以匹配空串,所以遍历直到找到了p中不是'*',后面的就都是false
                dp[0][j] = True
            else:
                break

        # 迭代求状态
        for i in range(1, targetStrLen + 1):
            for j in range(1, patternLen + 1):
                if p[j - 1] == '?':  # ?可以匹配任何字符所以看前面是否能匹配
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '*':  # 由于'*'可以匹配''或者任意字符串,因此先看空的情况是否匹配(dp[i-1][j]),然后再看将s的当前字符匹配(dp[i][j-1])
                    dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
                else:  # 当前p[j - 1]为 a - z 时，就要看s[i - 1] == p[j - 1]且要看前面的是否匹配(dp[i - 1][j - 1])
                    dp[i][j] = s[i - 1] == p[j - 1] and dp[i - 1][j - 1]
        return dp[-1][-1]

    def isMatch(self, s: str, p: str) -> bool:
        return self.isMatch2(s, p)


if __name__ == "__main__":
    s, p = "acdcb", "a*c?b"
    # s, p = "adceb", "*a*b"
    # s, p = "aa", "*"
    # s, p = "cb", "?a"
    print(Solution().isMatch(s, p))
